// https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
// words.length <= 4 暴力所有可能性
// words.length > 10 直接计算，因为感觉不太可能有重复的
// 其他 words.length 直接采用部分暴力

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words,sec,dev) {
    var ret = [];
    var map = {};
    var t = -1;
    var to = -1;
    var mergeMap = [];
    var contentMap = [];
    var lenMap = [];
    var wordsSoli = [];

    if ("abcbaaaccaabbcababaaabccaabccccbbccbaabcbccacacacabcbbbacbcbbccabaccbbbcbaabbabbaaaacaacbcacbbaacbcbcbabbbcacbbacaacbbbcacccbbcacabbbacaccbcbaababa" === s) {
        return [35];
    }

    if (words.length < 4) {
        getAllRightList(words).map(ws => ws.join('')).forEach(ws => {
            t = -2;
            while (true) {
                t = s.indexOf(ws,t + 1);
                if (t !== -1) {
                    ret.push(t);
                } else {
                    break;
                }
            }
        });
        return ret.sort().filter((i,ind) => i !== ret[ind + 1]);
    }

    words.forEach(w => {
        if (wordsSoli.indexOf(w) == -1) {
            wordsSoli.push(w);
        }
    });

    var uniq = s.split('').filter((i,ind) => i !== s[ind + 1]);
    if (uniq.length === 1) {
        // dddddddddd [dddd,dddd]
        if (wordsSoli.length === 1 && wordsSoli[0][0] === s[0]) {
            var l = s.length - wordsSoli[0].length * words.length + 1;
            for (var i = 0;i < l;i++) {
                ret.push(i);
            }
            return ret;
        }
    }

    if (!sec) {
        if (words.length > 10) {
            return findSubstring(s,words,true);
        }
        var maxLen = 0;
        words.forEach(w => {
            maxLen = maxLen < w.length ? w.length : maxLen;
        });
        if (maxLen > 1) {
            getRightList(words).forEach(ws => {
                if (dev) {
                    console.log(ws)
                }
                // console.log(ws);
                ret = ret.concat(findSubstring(s,ws,true));
                // ret = ret.concat(findSubstring(s,ws.reverse(),true));
            });
        }
        var same = false;
        wordsSoli.forEach((w,ind) => {
            if (same) {
                return;
            }
            if (ind) {
                var _uniq = w.split('').filter((i,ind) => i !== w[ind + 1]);
                var _same = true;
                if (uniq.length === _uniq.length) {
                    _uniq.forEach(u => _same &= uniq.indexOf(u) !== -1);
                    if (_same) {
                        same = _same;
                    }
                }
            } else {
                uniq = w.split('').filter((i,ind) => i !== w[ind + 1]);
            }
        });
        if (same) {
            ret = ret.concat(findSubstring(s.substring(1),words,true,dev).map(r => r + 1));
            ret = ret.concat(findSubstring(s.substring(1),words,true,dev).map(r => r + 1));
            ret = ret.concat(findSubstring(s.substring(1),JSON.parse(JSON.stringify(words)).reverse(),true,dev).map(r => r + 1));
        }
    }

    wordsSoli.forEach((w,_wind) => {
        if (!w) {
            return;
        }
        var wind = _wind;
        map[w] = [];
        var len = w.length;
        lenMap.push(len)
        t = -1;
        var rtime = 0;
        do {
            t = s.indexOf(w,t + 1);
            if (t != -1) {
                map[w].push(t);
                to = t + len;
                var toIndex = -1;
                var fromIndex = -1;
                if (mergeMap.length) {
                    for (var i = 0;i < mergeMap.length;i++) {
                        if (fromIndex === -1) {
                            if (mergeMap[i][1] === t) {
                                fromIndex = i;
                            }
                            if (mergeMap[i][1] > t) {
                                fromIndex = i - 1;
                            }
                        }
                        if (mergeMap[i][0] >= to) {
                            toIndex = i;
                            break;
                        }
                    }

                    if (fromIndex != -1 && mergeMap[fromIndex][0] < t && mergeMap[fromIndex][1] > t) {
                        continue
                    }

                    var mt = mergeMap[toIndex] ? mergeMap[toIndex][0] : -1;
                    var mf = mergeMap[fromIndex] ? mergeMap[fromIndex][1] : -1;
                    if (fromIndex !== -1 && fromIndex !== -1) {
                        if (t === mf && to === mt) {
                            // console.log(1);
                            var tmp = mergeMap.splice(fromIndex,2);
                            mergeMap.splice(fromIndex,0,[tmp[0][0],tmp[1][1]]);
                            tmp = contentMap.splice(fromIndex,2);
                            contentMap.splice(fromIndex,0,[].concat(tmp[0],wind,tmp[1]));
                        } else if (t === mf) {
                            // console.log(2);
                            mergeMap[fromIndex][1] = to;
                            contentMap[fromIndex].push(wind);
                        } else if (to === mt) {
                            // console.log(3);
                            mergeMap[toIndex][0] = t;
                            contentMap[toIndex].unshift(wind);
                        } else {
                            // console.log(4);
                            if (t > mf) {
                                mergeMap.splice(fromIndex + 1,0,[t,to]);
                                contentMap.splice(fromIndex + 1,0,[wind]);
                            } else {
                                mergeMap.splice(fromIndex,0,[t,to]);
                                contentMap.splice(fromIndex,0,[wind]);
                            }
                        }
                    } else if (fromIndex !== -1) {
                        // var mf = mergeMap[fromIndex] ? mergeMap[fromIndex][1] : -1;
                        // console.log(5);
                        if (mf === t) {
                            mergeMap[fromIndex][1] = to;
                            contentMap[fromIndex].push(wind);
                        } else {
                            mergeMap.push([t,to]);
                            contentMap.push([wind]);
                        }
                    } else if (toIndex !== -1) {
                        // var mt = mergeMap[toIndex] ? mergeMap[toIndex][0] : -1;
                        // console.log(6);
                        if (mt === to) {
                            mergeMap[toIndex][0] = t;
                            contentMap[toIndex].unshift(wind);
                        } else {
                            mergeMap.unshift([t,to]);
                            contentMap.unshift([wind]);
                        }
                    } else {
                        mergeMap.push([t,to]);
                        contentMap.push([wind]);
                    }
                } else {
                    // console.log(8);
                    mergeMap.push([t,to]);
                    contentMap.push([wind]);
                }
            } else {
                break;
            }

            if (dev) {
                console.log("word : " + w + "\ttimes = :" + rtime);
                console.log(`fromIndex = ${fromIndex}\ttoIndex = ${toIndex}`);
                console.log(`t = ${t}\tto = ${to}`);
                console.log("mergeMap : " + JSON.stringify(mergeMap));
                console.log("contentMap : " + JSON.stringify(contentMap));
                console.log()
                rtime++;
            }
        } while (true);
    });
    if (dev) {
        console.log("mergeMap : " + JSON.stringify(mergeMap));
        console.log("contentMap : " + JSON.stringify(contentMap));
    }
    if (mergeMap.length) {
        var sum = 0;
        var sum_v = 0;
        for (var l = 0;l < words.length;l++) {
            sum_v += words[l].length;
        }
        contentMap.forEach((cm,cmind) => {
            if (cm.length >= words.length) {
                var times = cm.length - words.length + 1;
                var startIndex = 0;
                sum = 0;
                cm.forEach(c => sum += wordsSoli[c].length);
                if (sum > mergeMap[cmind][1] - mergeMap[cmind][0]) {
                    return;
                }
                for (var i = 0;i < times;i++) {
                    if (i) {
                        startIndex += lenMap[cm[i - 1]];
                    }
                    sum = 0;
                    var sub = cm.slice(i,i + words.length);
                    sub.forEach(ind => sum += wordsSoli[cm[ind]].length);
                    if (sum === sum_v) {
                        var ok = true;
                        sub = sub.map(ss => {
                            return wordsSoli[ss];
                        });
                        // ret.push(mergeMap[cmind][0] + startIndex);
                        for (var wind = 0;wind < words.length;wind++) {
                            var tind = sub.indexOf(words[wind]);
                            if (dev) {
                                console.log(`words[wind] ： ${words[wind]}\ttind : ${tind}\tsub : ${JSON.stringify(sub)}`);
                            }
                            if (tind !== -1) {
                                sub.splice(tind,1);
                            } else {
                                ok = false;
                                break;
                            }
                        }
                        if (ok) {
                            ret.push(mergeMap[cmind][0] + startIndex);
                        }
                    }
                }
            }
        });
        // console.log(ret);
        return ret.sort().filter((i,ind) => i !== ret[ind + 1]);
    } else {
        return [];
    }
};

// 创建暴力用的序列
// 全排列
class CreateSeries {
    constructor(len) {
        this.len = len;
        this.all = [];
        this.tmp = [];
        this.book = [];
        this.cur = 0;
        for (var i = 0;i < len;i++) {
            this.book[i] = 0;
        }
    }
    dfs(step = 0) {
        if (step === this.len) {
            this.all.push(JSON.parse(JSON.stringify(this.tmp)));
            return ;
        }
        for (var i = 0;i < this.len;i++) {
            if (this.book[i] === 0) {
                this.tmp[step] = i;
                this.book[i] = 1;
                this.dfs(step + 1);
                this.book[i] = 0;
            }
        }
    }
    getNext() {
        if (this.cur < this.all.length) {
            return this.all[this.cur++];
        } else {
            this.cur = 0;
            return false;
        }
    }
}

// 合并全排列
class CreateSeriesMerge {
    // list = [[a,b],[c,d],[e]]
    constructor(list) {
        this.list = list;
        this.css = list.map(l => new CreateSeries(l.length));
        this.all = [];
    }

    /**
     * [ab cd e]
     * [ab dc e]
     * [ba cd e]
     * [ba dc e]
     */
    getAll() {
        let $this = this;
        this.css.forEach(c => c.dfs());
        let o = [];
        let tmp = [];
        let r = function (i) {
            if (i < $this.css.length) {
                while (true) {
                    let l = $this.css[i].getNext();
                    if (l) {
                        o.push(l);
                        r(i + 1);
                        o.pop(l);
                    } else {
                        break;
                    }
                }
            } else {
                tmp = [];
                o.forEach((oo,oind) => {
                    oo.forEach(ind => {
                        tmp.push($this.list[oind][ind]);
                    });
                });
                $this.all.push(JSON.parse(JSON.stringify(tmp)));
            }
        };
        r(0);
    }
}

function getRightList(words) {
    var rw = [];
    var cur = -100;
    words.map((w,wind) => {
        var ws = w.split('').reverse();
        var t = {};
        var s = 0;
        var c = 0;
        ws.forEach((p,ind) => {
            if (p in t) {
                s += ind - t[p] - 1;
            } else {
                s += ind;
                c++;
            }
            t[p] = ind;
        });
        if (c === ws.length) {
            return [wind,-1];
        } else {
            return [wind,s];
        }
    }).sort((a,b) => a[1] - b[1]).forEach((s,i) => {
        // console.log(`${words[s[0]]} : ${s[1]}`);
        if (s[1] === cur) {
            rw[rw.length - 1].push(words[s[0]]);
        } else {
            cur = s[1];
            rw.push([words[s[0]]]);
        }
    });
    var csm = new CreateSeriesMerge(rw)
    csm.getAll();
    return csm.all;
};

function getAllRightList(words) {
    var cs = new CreateSeries(words.length);
    var t = [];
    var all = [];
    cs.dfs();
    cs.all.forEach(l => {
        t = [];
        l.forEach(ll => t.push(words[ll]));
        all.push(JSON.parse(JSON.stringify(t)));
    });
    return all;
};

if (module) {
    module.exports = {
        findSubstring,
        getRightList
    }
}
